#!/usr/bin/python3
# -*- coding: UTF-8 -*-

#在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

#第一种 递归法
# 递归方式实现 生成前12项,100以内

def fib_recur(n):
    assert n >= 0, "n > 0"
    if n <= 1:
        return n
    return fib_recur(n-1) + fib_recur(n-2)

print("====== This is result A! ====== ")
for i in range(1, 12):
    print(fib_recur(i), end = '\n ')

def Fib_1(N):
    f = 1
    i = 0
    g = 0
    for i in range(N):
        f = f + g
        g = f - g
        i =  i +1
    return f

if __name__ == '__main__':
    print("====== This is result B! ====== ")
    for i in range(11):
        print(Fib_1(i), end = '\n')

def Fib_2():
    print("====== This is result C! ====== ")
    lis = []
    for i in range(11):
        if (i == 0 or i == 1):     #第1,2项 都为1
            lis.append(1)
        else:
            lis.append(lis[i-2] + lis[i-1])    #从第3项开始每项值为前两项值之和
    print(lis)

if __name__ == '__main__':
    Fib_2()

# 第二种 递推法
# 递推法，就是递增法，时间复杂度是 O(n)，呈线性增长，如果数据量巨大，速度会越拖越慢
# Fibonacci series: 斐波纳契数列
# 两个元素的总和确定了下一个数

a, b = 0, 1
print("====== This is result D! ====== ")
while b < 100:
    print(b)
    a, b = b, a+b


